package duplicateZeros;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Stack;

public class Solution {

    // 暴力
//    public void duplicateZeros(int[] arr) {
//        int index = 0;
//        int i = 0;
//        while(index<arr.length){
//            if(arr[i]!=0){
//                arr[index] = arr[i];
//                i++;
//            }else {
//                copy(i+1,arr);
//                arr[index] = 0;
//                arr[index++] = 0;
//                i+=2;
//            }
//            index++;
//        }
//    }
//    private void copy(int i,int []arr){
//        int t = arr[i];
//        for (int j = i+1; j <arr.length ; j++) {
//            int tmp = arr[j];
//            arr[j] = t;
//            t = tmp;
//        }
//    }


    public void duplicateZeros(int[] arr){
        // 双指针

        // 模拟栈
        // 栈的写法
//        Stack<Integer> stack = new Stack<>();
//        for (int i = 0; i < arr.length; i++) {
//            stack.push(arr[i]);
//            if(arr[i] == 0){
//                stack.push(0);
//            }
//        }
//        int n = arr.length;
//        while(stack.size()>n){
//            stack.pop();
//        }
        // 双指针实现
        // 思路 模拟栈的操作
        //
        int top = 0;
        int i = -0;
        int n = arr.length;
        while(top<n){
            i++;
            if(arr[i] == 0){
                top+=2;
            }else {
                top++;
            }
        }
        int j = n-1;
        // 处理边界情况 如果最后一个元素 == 0那么只复写一次
        if(top == n+1){
            arr[j] = 0;
            j--;
            i--;
        }
        while (j>=0){
            if(arr[i] == 0){
                arr[j] = 0;
                arr[--j] = 0;
            }else {
                arr[j] = arr[i];
            }
            i--;
            j--;
        }
    }
}
